#include<bits/stdc++.h>
using namespace std;
#define int long long

vector<int> TenToThree(int x) {
	vector<int> ans;
	while (x) {
		ans.push_back(x % 3);
		x /= 3;
	}
//	reverse(ans.begin(), ans.end());
	return ans;
}

int ThreeToTen(vector<int> x) {
	int ans = 0;
//	reverse(x.begin(), x.end());
	int t = 1;
	for (int i : x) {
		ans += i * t;
		t *= 3;
	}
	return ans;
}

signed main() {
	int v, q;
	cin >> v >> q;

	vector<int> s =  TenToThree(v);

	while (q--) {
		int op, k;
		cin >> op >> k;

		if (k >= s.size()) {
			int num = k - s.size() + 1;
			while (num--)
				s.push_back(0);
		}

		if (op == 1) {
			s[k] = (s[k] + 1) % 3;
		} else if (op == 2) {
			if (s[k] == 0)
				s[k] = 2;
			else if (s[k] == 1)
				s[k] = 0;
			else
				s[k] = 1;
		} else {
			if (s[k] == 1)
				s[k] = 2;
			else if (s[k] == 2)
				s[k] = 1;
		}
		for (int i : s)
			cout << i;
		cout << endl;
		cout << ThreeToTen(s) << endl;
	}
	return 0;
}
